﻿using System;

public class InsertionSort
{
    public static void Main()
    {
    }

    public int[] Sort(int[] unsortedArray)
    {
        int[] sortedArray = new int[unsortedArray.Length];
        Array.Copy(unsortedArray, sortedArray, unsortedArray.Length);
        for (int i = 1; i < sortedArray.Length; i++)
        {
            int key = sortedArray[i];
            int j = i - 1;
            while (j > 0 && sortedArray[j] > key)
            {
                sortedArray[j + 1] = sortedArray[j];
                j--;
            }
            sortedArray[j + 1] = key;
        }
        return sortedArray;
    }
}